The matching of two or more planar point patterns is an important technique in the field of computer vision technology and in the image processing technology. When an image is input into a computer in a digitized format, the "feature points" of the image can be abstracted with the conventional feature abstracting technologies, according to the characters of the image or to the purposes of the processing. The feature points, more concretely, the coordinates of the points, so obtained can be used in the recognition of the image. For example, by matching the distribution of the feature points, the similarity of the patterns comprising the feature points can be calculated, so that the similarity of the images can be decided.
A good example of the application of the pattern matching technology is the recognition of fingerprints. When the image of a fingerprint is scanned by an image scanner, the image is digitized and input to a computer. The computer uses a software to abstract the distribution of the feature points of the fingerprint, usually the terminals and the cross points of the lines of the fingerprint. By matching two patterns comprising feature points obtained in different time or places, whether the two fingerprints came from the same finger, can be decided.
In the matching of two planar point patterns so obtained, several problems will be faced. One is, the number of feature points of two patterns could be different, even if they were abstracted from a same image or image source. Another is, the possibility that the same feature point exists at the same position in both patterns can not be forecast. The third is, while the images (patterns) were obtained at different time and/or places, the distribution of the feature points in one pattern could be shifted, rotated and/or distorted (enlarged or reduced), if compared with the other pattern.
Taiwan patent application No. 79109743 (corresponding to U.S. Pat. No. 5,392,367) related to a "Planar Pattern Point Matching and Recognition Method and Device thereof" wherein a "fuzzy relaxation" approach is introduced.
According to said patent, the matching of two planar point patterns are conducted in two steps. The first step is to mate the points of one pattern (the reference pattern) with the points of another pattern (the test pattern). The second step is to calculate the similarity of the two patterns.
In the mating process, a "course matching" approach is used to exclude pairs of points that are impossible to be mated. The "mating possibility" of one point from the reference pattern to be mated with one point from the test pattern is set at 0 for those pairs that can not be mated and is set at 1 for other pairs. The mating possibility of a pair is then adjusted according to "the value of other mated pairs to support such mating, given that such one pair is mated". The mating possibility of one mated pair is calculated to the following equation: ##EQU1## wherein S.sup.(r) (pi,qj) represents the mating possibility of points pi and qj, when it is adjusted for the r.sup.th time, pi represents a point from the test pattern P, qj represent a point from the reference pattern Q, Cij(h, k) represents the value that another mated pair ph and qk to support the mating of pi and qj wherein ##EQU2## l's represent distances between pi and ph or between qj and qk and m represents the least number of points in patterns P and Q.
While the mating possibility of every point from the reference pattern with every point from the test pattern is calculated, the best mated pairs can be selected with a "sequential forward selection method".
In the second step, the similarity of the reference pattern and the test pattern can be calculated employing the following components. They are: the mated rate (number of mated pairs/minimum number of points of the two patterns), the average mating possibility, the average distance of mated pairs and the scaling factor.
In order to solve the problem of distortion, including shift, rotation and proportional scaling, a "least mean-square-error" value was introduced to adjust the distribution of the test pattern.
Although the above-said patent taught an automatic matching method for planar point patterns with high efficiency, it inherits the problem of relatively high rejection rate. If the "false acceptance rate--FAR" is set at 0.1%, in matching 800 fingerprint images, its "false rejection rate--FRR" will be about 25%. This means, when two images are from the same fingerprint, the possibility that the system decides they are not from the same fingerprint is 25%.
It is then necessary to develop an automatic matching device and method for planar point patterns wherein the FRR can be reduced. It is also necessary to have an automatic matching device and method that provide higher efficiency.